package com.hanxiaozhang.no10leetcode.array;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * <p>
 * 给定一个正序排列的整型数组，找到目标元素的起始和终止位置，如果在数组中没有找到目标元素，返回[-1, -1]
 * 算法复杂度要求为O(log n)
 * 示例1:
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: [3,4]
 * 示例2:
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: [-1,-1]
 * <p>
 * 思路：三次调用二分法
 * 1. 第一次找到是否存在该目标数。
 * 2. 如果存在该目标数，再分别从 [0,目标数位置]  和 [目标数位置, nums.length - 1]  进行二分查找，确定开始结束位置。
 *
 * @author hanxinghua
 * @create 2024/1/11
 * @since 1.0.0
 */
public class No34FindFirstAndLastPositionOfElementInSortedArray {


    public static void main(String[] args) {


        int[] nums = {5, 7, 7, 8, 8, 10};
        int target = 5;

        System.out.println(Arrays.toString(method1(nums, target)));

        System.out.println(Arrays.toString(method2(nums, target)));

    }


    /**
     * 方法2
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] method2(int[] nums, int target) {

        int index = dichotomic(nums, 0, nums.length - 1, target);
        int[] result = {-1, -1};
        if (index > -1) {
            result[0] = dichotomic(nums, 0, index, target);
            result[1] = dichotomic(nums, index, nums.length - 1, target);
        }
        return result;
    }

    /**
     * 二分法
     *
     * @param nums
     * @param left
     * @param right
     * @param target
     * @return
     */
    private static int dichotomic(int[] nums, int left, int right, int target) {
        int mid = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            if (target == nums[mid]) {
                return mid;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }


    /**
     * 方法1
     *
     * @param nums
     * @param target
     * @return
     */
    private static int[] method1(int[] nums, int target) {

        // 二分法找target的index
        int index = -1;
        int left = 0, right = nums.length - 1, mid = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            if (target == nums[mid]) {
                index = mid;
                break;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        int[] result = {-1, -1};
        // 存在值目标值时，分别从左右两侧开始找
        if (index > -1) {
            for (int i = index; i < nums.length; i++) {
                if (nums[i] == target) {
                    result[1] = i;
                }
            }
            // 注意 i >= 0
            for (int i = index; i >= 0; i--) {
                if (nums[i] == target) {
                    result[0] = i;
                }
            }
        }
        return result;
    }
}
